/* 
 * Matrix Chain Multiplication. The goal to solve this problem is find an order for multiplying matrics that has the lowest cost. 
 *
 * matrix    |    A1     A2    A3    A4     A5    A6
 * -----------------------------------------------------
 * Dimension |  30*35  35*15  15*5  5*10  10*20  20*25
 *------------------------------------------------------
    P        |  p0*p1  p1*p2  p2*p3 p3*p4 p4*p5 p5*p6

 * The solution for matrix chain {Ai*Ai+1*...Aj} is defined as follows:
 * m[i,j] = min{m[i,k]+m[k+1,j]+Pi-1*Pk*Pj}   if i<j 
 *          0                                 if i==j
 * matrix Ai can be represented as Pi-1 * Pi
 */

#include <iostream>
using namespace std;

int p[7] = {30,35,15,5,10,20,25};

int maxInt = 2^31;

int min(int a, int b)
{
	return ((a<b)?a:b);
}


//==============================================================================
// Bottom up method
 
void matrix-multiply(matrix* mat, int len)
{
	// Create two dimension array
	int **m = new int*[len+1]; // store cost
	int **step = new int*[len+1]; // store step
	int i;
	for(i=0;i<len+1;i++)
	{
		int m[i] = new int[len+1];
		int step[i] = new int[len+1];
	}
	// m[i,i] should be 0
	for(i=0;i<len+1;i++)
	{
		m[i][i] = 0;
	}
	int l;	// the length of sub chain
	for(l=2;l<=n;l++)
	{
		for(i=1;l<=n-l+1;i++)
		{
			j = l+i-1;
			m[i][j] = maxInt; 
		}
			int k;
			int opt;
			for(k=i;k<j;k++)
			{
				opt = m[i][k]+[k+1][j]+mat[i-1]*mat[k]*mat[j];
				if(opt < m[i][j])
				{
					m[i][j] = opt;
					step[i][j] = k;
				}
			}
	}

}

//==============================================================================
// Construct solution

Print-Optimal-Parens(s,i,j)
{
	if i==j
	   print Ai
	else
	  print (
	  print-Optimal-Parens(s,i,s[i,j]);
	  print-optimal-parens(s,s[i,j]+1,j);
	  print )
}


int main()
{
	return 0;
}
